package com.zs.letcode.path_problems_in_dynamic_programming;

/**
 * 1289. 下降路径最小和 II
 * 给你一个整数方阵arr，定义「非零偏移下降路径」为：从arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
 * <p>
 * 请你返回非零偏移下降路径数字和的最小值。
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：13
 * 解释：
 * 所有非零偏移下降路径包括：
 * [1,5,9], [1,5,7], [1,6,7], [1,6,8],
 * [2,4,8], [2,4,9], [2,6,7], [2,6,8],
 * [3,4,8], [3,4,9], [3,5,7], [3,5,9]
 * 下降路径中数字和最小的是[1,5,7] ，所以答案是13 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= arr.length == arr[i].length <= 200
 * -99 <= arr[i][j] <= 99
 * 相关标签
 * 数组
 * 动态规划
 * 矩阵
 * <p>
 * 作者：宫水三叶
 * 链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/r8oh2h/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/11/1 21:44
 */
public class Chapter6 {
    public static void main(String[] args) {

    }

    private class Solution {
        /**
         * 方法一：动态规划
         *
         * @param grid
         * @return
         */
        public int minFallingPathSum(int[][] grid) {
            int n = grid.length;
            int[][] f = new int[n][n];
            // 初始化首行的路径和
            for (int i = 0; i < n; i++) {
                f[0][i] = grid[0][i];
            }
            // 从第一行进行转移
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    f[i][j] = Integer.MAX_VALUE;
                    int val = grid[i][j];
                    // 枚举上一行的每个列下标
                    for (int p = 0; p < n; p++) {
                        // 只有列下标不同时，才能更新状态
                        if (j != p) {
                            f[i][j] = Math.min(f[i][j], f[i - 1][p] + val);
                        }
                    }
                }
            }

            // 在所有的 f[n - 1][i] 中取最小值
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                ans = Math.min(ans, f[n - 1][i]);
            }
            return ans;
        }
    }
}
